package code.sort;

/**
 * @ClassName KthSmallest
 * @Description O(n)时间复杂度内求无序数组中第K大的元素. 比如 4、2、5、12、3 第3大元素为4
 * @Author za-zhouyunxing
 * @Date 2019/9/29 18:40
 * @Version 1.0
 */
public class KthSmallest {

    public static int  kthSmallest(int[] a, int k){
        if (a == null || a.length < k){
            return -1;
        }
        //获取分区点
        int partition = partition(a, 0, a.length - 1);
        while (partition + 1 != k){
            if (partition + 1 < k){
                partition = partition(a, partition + 1, a.length -1);
            }else {
                partition = partition(a, 0, partition - 1);
            }
        }
        return a[partition];
    }

    private static int partition(int[] a, int p, int r) {
        int pivot = a[r];
        int i = p;
        for (int j = p; j < r; j++) {
            // 这里要是 <= ，不然会出现死循环，比如查找数组 [1,1,2] 的第二小的元素
            if (a[j] <= pivot){
                swap(a, i, j);
                i++;
            }
        }
        swap(a, i, r);
        return i;
    }

    private static void swap(int[] arr, int i, int j) {
        if (i == j) {
            return;
        }

        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] array = new int[]{3, 4, 2, 1, 5, 6, 7, 8};
        System.out.println(kthSmallest(array, 4));
    }
}
